package com.java.multipledatasource.algorithm;

import java.util.Stack;

/**
 * @author hu
 * @version 1.0
 * @date 2021/1/23 0023 下午 1:56
 * @description 快慢指针
 */
public class LinkListMid {
    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }

    }

    /**
     * 链表长度如果是奇数 返回中间节点 如果是偶数返回 上中节点
     *
     * @param head
     * @return
     */
    public static Node midOrUpMidNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 链表长度如果是奇数 返回中间节点 如果是偶数返回 下中节点
     *
     * @param head
     * @return
     */
    public static Node midOrDownMidNode(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node fast = head.next;
        Node slow = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 链表长度如果是奇数 返回中间节点 如果是偶数返回  上中节点的前节点
     *
     * @param head
     * @return
     */
    public static Node midOrUpMidPreNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node slow = head;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 链表长度如果是奇数 返回中间节点 如果是偶数返回  下中节点的后节点
     *
     * @param head
     * @return
     */
    public static Node midOrDownAfterNode(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node slow = head.next;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 判断链表是否回文
     *
     * @param head
     * @return
     */
    public static boolean checkPalindrome(Node head) {
        if (head == null) {
            return false;
        }
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }


    // 一个链表 一个指定目标数字 大于放后侧 小于放前侧 等于放中间

    // 给定两个可能有环的单列表 如果相交返回第一个相交的节点 如果不相交返回null


    //判断链表是否有环 借助 set
    //判断链表是否有环 快慢指针 如果有环 在第一次相交后 快指针回到头节点 一步一步走，同时慢指针继续，会继续相遇在头节点

    //   判断两个无环单链表是否相交 判断两个尾节点是否想等
    //   判断两个无环单链表是否相交，如果相交返回相交的第一个节点 判断两个尾节点是否想等，相等 长链表为cur1 短练笔为cur2
    //     长链表先走 差值决定值步，后一起走则第一个相交
    //   一个链表有环 一个链表无环不会相交，两个有环链表相交 公用环

    public static boolean isLoopLink(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return  false;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) {
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return  false;
    }

    /**
     * 如果链表存在环 返回入环节点
     * @param head
     * @return
     */
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return  null;
        }
        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        fast = head;
        while (fast != slow ) {
            fast = fast.next;
            slow = slow.next;
        }
        return  fast;
    }

    public static Node reverseNode(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node next;

       while (head != null ){
           next = head.next;
           head.next = pre;
           pre = head;
           head = next;
       }

        return pre;
    }


    public static Node resNode(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node node = null;
        Node next = null;

        while (head != null){
            next = head.next;

            head.next = node;
            node = head;

            head = next;
        }

        return node;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
//        n6.next = n3;

//        System.out.println(isLoopLink(n1));
//        Node loopNode = getLoopNode(n1) ;
//        if (loopNode == null) {
//            System.out.println("null");
//        } else {
//            System.out.println(loopNode.value);
//        }

        Node node = resNode(n1);
        System.out.println(node.value);
        System.out.println("111");
    }


}
